The present invention relates to computer systems; more particularly, the present invention relates to executing memory transactions using a linked list.
The efficiency of accessing large arrays of a memory device can be improved by enabling out of order accesses of the memory. Typically, larger memory arrays are divided into banks. A bank is a section of memory wherein an access is completed before another access to the same bank can be started. In particular, whenever two transactions access the same bank, the second transaction must wait the full memory access time of the first transaction before it can begin. However, an access to one bank does not delay access to other banks within the memory device. As a result, if two transactions are accessing different banks, a second transaction may begin as soon as it has been received at the memory device. This hides some of the memory access time.
Therefore, in order to further improve access efficiency, transactions to different banks should be done out of order. For example, if three memory transaction are received, the first two to the same bank and the third to a different bank. The first transaction is started but the second is held up because it is to the same bank. Thus, if the transactions were executed in order, the third transaction would also be held up. However, if the transactions are enabled to execute out of order, the third transaction could be started as soon as it was received.
To allow out of order executions, control logic must store the transactions that are stalled and keep track of these stalled transactions until they can be executed. A simple approach is to use a set of first-in-first-out (FIFO) buffers. Each FIFO within the controller may hold the transactions for one bank. Subsequently, an arbiter may select which transaction in a non-empty FIFO will next be executed.
The problem with the above memory mapping method is the number and size of the FIFOs. For a very large memory array, there is typically a large number of banks. Thus, for maximum performance, a FIFO for each bank is required. For instance, a typical memory may be divided into 32 read banks and 4 write banks, resulting in 36 FIFOs. The size of each of the 36 FIFOs is dependent on the number of transactions that may be received. In some applications, the maximum number of transaction that can be handled is 64. Since it is possible for all 64 transactions to go to the same bank, each bank must be capable of storing 64 transactions at one time. As a result, 36 FIFOs requiring 64 storage locations are often required. Providing this amount of storage space for the execution of out of order transactions results in an inefficient use of resources within a computer system. Therefore, a more efficient method and apparatus handling out of order memory transactions is desired.